1. Field of the Invention
The present invention relates to digital printing devices, and in particular, to a technique for reducing the amount of ink and processing time required for printing.
2. Description of the Related Art
Most computer-driven printing devices which generate hard copy on an output media, such as laser, dot-matrix and ink-jet printers, print in a binary fashion--the output medium is divided into an array of picture elements or "pixels" and the devices can either print a small colored dot at each pixel location or leave the pixel location blank. In the case of monochrome printers, all of the dots are printed with a single color whereas with color printers a dot color is chosen from a small set of colors. In any case, the dot itself has a uniform color so that the resulting output consists of an array of colored and blank pixels.
Pictorial images such as those produced by photographic techniques or by computerized imaging systems, by contrast, are continuous in tonality. If such an image is divided into pixels, each pixel exhibits a "grayscale" color whose tonal value falls within a range of tonal values. In order to reproduce such "continuous-tone" images by means of electronic printing, the images must therefore be converted into a form which is suited to the characteristics of the printing device, generally a binary format. This conversion process, which may take many forms, is generically referred to as "halftoning." Although a halftone image actually consists solely of a spatial pattern of binary pixels (colored or blank dots), the human visual system integrates this pattern to create an illusion of a continuous-tone image.
During the printing process, the image to be printed is divided into a series of pixels and the value of the image in each pixel is quantized to produce a multi-bit digital word which represents the tonal value of the pixel. The image is thus converted to a stream of digital words which are provided to the printing device. In order to convert the format of each word into a format suitable for reproduction on the digital device, halftoning is performed on the digital word stream during a process called "preprocessing". Numerous halftoning techniques have been developed and refined over the years. In their simplest form, such techniques compare the value of each digital word with a threshold level, and generate a binary output pixel value depending on the relative values.
For example, a digital scanner processing a continuous-tone image might generate a stream of multi-bit words representing the detected light intensities. Commonly, the numerical value of these words ranges from 0 to 255, corresponding to a 256-level gray scale or an eight-bit word. If such a digital word stream is to be reproduced on a binary printing device, the halftoning process compares the scanner output words with a either a single threshold value or an array of threshold values to produce the required binary output pixel stream. In such a system, each 8-bit scanner word has effectively been compressed into a single-bit output word.
Naturally, such compression produces a significant loss of visual information and, in turn, creates distortions in the reproduced image that are not present in the original image. Additional techniques have therefore been developed to reduce the visual distortions created by the halftoning process. One approach, known as "error diffusion", attempts to "diffuse" the "quantization error" (i.e., the difference between the input value represented by a multi-bit word and the output value represented by a single bit or two multi-bit words) proportionally among neighboring pixels.
This diffusion is performed by adding a portion of the quantization error to the input values of the next pixel in the processing line and to neighboring pixels in the following line or lines. The quantization error is added to the pixel values before processing so that the quantization error is "spread" over several pixels.
In accordance with one embodiment of the error diffusion process, the input pixels represented by the input words are processed in "raster" order (line-by-line with each line being processed from left to right before the next lower line is processed). In general with a left-to-right processing order, the error diffusion process produces an excellent image reproduction, but also creates well-known artifacts called "worms" and "snowplowing" which degrade image quality. The "worms" appear as curved or straight diagonal lines in areas of uniform gray and produce a patterned appearance in the halftoned image. Consequently, various techniques have been used to reduce or eliminate these kinds of artifact patterns.
Some of these known techniques, described, for example, in U.S. Pat. No. 4,955,065, Japanese Laid-Open Patent HEI 4-37256/92 and Japanese Laid-Open Patent HEI 4-51773/92, vary the processing sequence from the conventional raster scan pattern (where each of the pixels in each line of the image are processed left-to-right and the lines are processed in a top-to-bottom order) to a serpentine scan pattern where the pixel lines are still processed from top-to-bottom, but alternate pixel lines are processed in opposite directions. This technique re-orients the worms so that they appear as horizontal lines in uniform gray areas of the image and are thus less obtrusive; however they are still present to the same degree as when the conventional raster scan is used.
Another known method, described in Japanese Laid-Open Patent HEI 3-151762/91, of minimizing the appearance of worms also varies the processing sequence from the conventional raster pattern. In accordance with one embodiment, the processing direction for each image line is selected based on the output of a random number generator or noise pattern generator which is quantized to yield a stream of "1's" and "0's". Pixel processing for each line is therefore performed left-to-right (in response to a "1") or right-to-left (in response to a "0") in a random pattern. In accordance with another known embodiment, pixels in image lines are processed left-to-right and right-to-left in predetermined periodic patterns, e.g., two left-to-right scans, followed by two right-to-left scans, and so on. While these prior processing order techniques reduce the size of the worms, the worms are still visible in the halftoned image.
Another problem inherent in the error-diffusion method is the large number of computations necessary to process an image. Since several computations, including multiplications, must be performed on each processed pixel, millions of computations may be necessary to generate the final output values for a typical high-resolution image. In addition, it is necessary to store at least one line of error values that are to be applied to the succeeding line of image values. This large number of computations and the required storage combine to increase the processing time for each image, resulting in decreased printer throughput.
As a result, alternatives to error diffusion have been developed to reduce the number of computations necessary to process an image. One such alternative is called "ordered dithering," in which an array of predetermined (and generally different) threshold values--a "dither array"--with the same spacing as the image pixels is conceptually overlaid onto the image pixel array. If the dither array is smaller than the image array, then the dither array is repeated side-by-side or "tiled" over the image array to produce a repetitive pattern. Each pixel thus has two values conceptually associated with it, namely, the actual pixel tonal value and the threshold value of the overlaid dither array cell to which it is compared. Equivalently, the values in the dither array can be added to the tonal value of each pixel, and the augmented value compared with a fixed threshold. In either case, an output value is generated based on the comparison. Since the processing of each pixel involves only a simple comparison and is independent of neighboring pixel values, the computation time required to process an entire image is substantially less than that required for error diffusion.
However, the quality of the resulting processed image depends entirely on the threshold values chosen for the dither array. Two types of dither arrays are commonly used. In a "clustered-dot" dither array, the threshold values are organized into small groups having closely spaced values. These clusters mimic "dots" of various sizes, and thus produce processed images visually similar to those produced by the traditional halftone screen used for many years in photoengraving processes.
In "dispersed-dot" dithering, large and small threshold values are spread even throughout the array. This technique enhances the printable gray scale as well as resolution. For image-reproduction devices capable of clearly displaying a single isolated pixel, the dispersed-dot dither array usually produces better image quality than the clustered-dot dither array; this is because dispersed-dot arrays achieve better high-frequency fidelity and create a better illusion of a continuous gray region than do clustered-dot arrays of the same resolution and period.
With both types of arrays, a tradeoff generally exists between the number of discrete gray levels that can be represented (which increases as the number of dither-array elements or cells increases) and the appearance of annoying low-frequency geometric patterns in areas of uniform gray (which also appear as the number of dither-array elements increases). Increasing the size of the dither array also tends to decrease image resolution as low-frequency values disappear. One way to reduce these patterns while retaining resolution is to make the size of the dither array very large and utilize homogeneous patterns of threshold values, where successive threshold values "turn on" pixels in a homogeneous, random pattern. However, as the array size increase, assigning threshold values to the array cells to produce the necessary pattern becomes a non-trivial matter. Accordingly, various schemes have been developed to derive random value sequences and assign them to the array cells.
One common technique used to create a homogenous ordered dither array is called "recursive tessellation". The goal of recursive tessellation is to assign threshold values to each of the dither array cells in such a way that, as each successive cell is numbered or "turned on", the two-dimensional array of "on" cells is as homogeneously arranged as possible. Thus, when the dither array is used as a threshold array in a halftoning process, the corresponding arrangement of output binary dots will be disbursed as homogeneously as possible for each gray level to be simulated.
The algorithm used in recursive tessellation for generating the threshold array is based on the fact that if a regular geometric shape or "tile" is used cover or tessellate the two-dimensional dither array, the center point of the shape and its vertices can serve as center points for a retessellation of the array with new tiles of the same geometric shape but sized one cell smaller. In turn, the center points and vertices of these new tiles can act as center points for another retessellation with tiles that are again one cell smaller.
In accordance with the recursive tessellation algorithm, all of the tile vertices at each stage of this recursive tessellation are assigned threshold numbers before the next tessellation takes place. The algorithm provides a mechanism for locating a family of points that are exactly in the center of voids which occur between the vertex points of the tiles. Essentially, new points are added in the largest "voids" or areas where there is an absence of "on" pixels. The recursive tessellation method and the resulting threshold arrays are described in detail in "Digital Halftoning" by Robert Ulichney, printed by the MIT Press, Cambridge, Mass. and London, England, 1990, pages 128-171. While the recursive tessellation method can produce large dither arrays, these arrays suffer from a strong periodic structure that imparts an unnatural appearance to the resulting images when the arrays are used in a conventional halftoning operation.
Consequently, other conventional methods have been developed to generate dither arrays and one of these conventional methods is called a "blue noise mask". In general, "blue noise" is the high-frequency portion of a white noise spectrum. The power spectrum of blue noise has a low-frequency cutoff and is flat out to some fine high frequency limit. In general, the dot patterns produced by a blue noise mask are aperiodic and radially symmetric and these patterns produce an aperiodic, uncorrelated dither array structure without low frequency graininess. The choice of a blue noise mask arose from studies of the frequencies present in dot patterns produced by the error diffusion process described previously. When these dot patterns are converted into to a power spectrum of power versus frequency, it can be seen that the power spectrum has a low frequency cutoff point which occurs in the blue light frequency range, hence the name "blue noise".
The shape of the power spectrum can be used to construct dither arrays by examining dot patterns which produce blue noise power spectra and creating dither arrays from these dot patterns. The resulting arrays produce a high-quality output, however, the conversions between the frequency and spatial domains necessary to derive the arrays produces a complicated algorithm for generating the dither arrays. Blue noise masks are described in more detail in "Digital Halftoning Using A Blue Noise Mask", T. Mitsa and K. Parker, Proceedings SPIE, Image Processing Algorithms And Techniques II, v.1452, pps. 47-56, Feb. 21-Mar. 1, 1991.
Another conventional technique for generating a large, homogeneous dither array is called the "void-and-cluster method". Again, the goal of this latter method is to produce a homogeneous distribution of 1's and 0's by starting with an initial pattern and removing pixels from the center of the tightest "clusters" and inserting them into the largest "voids". The void-and-cluster method is described in detail in "The Void-and-Cluster Method For Dither Array Generation", Robert Ulichney, IS&T/SPIE Symposium on Electronic Imaging Science and Technology, San Jose, Calif., Feb. 3, 1993 and "Filter Design For Void-and-Cluster Dither Arrays", Robert Ulichney, Society for Information Display International Symposium, San Jose, Calif., Jun. 14-16, 1994, the contents of which are hereby incorporated by reference.
In particular, in accordance with the aforementioned articles, the initial pattern used to generate the dither arrays is called a "Prototype Binary Pattern" and the terms "cluster" and "void" are defined in terms of "minority pixels" and "majority pixels". When less than half of the pixels in the Prototype Binary Pattern are of a particular type (either "1's" or "0's") they are denoted as minority pixels and the other type of pixel is denoted as a majority pixel. Using these definitions of minority and majority pixel, the terms "cluster" and "void" refer to the arrangement of minority pixels on a background of majority pixels. In particular, a "void" is a large space between minority pixels and a "cluster" is a tight grouping of minority pixels. During the processing of the Prototype Binary Pattern, minority pixels are always added to the center of the largest voids and are removed (or replaced with a majority pixel) from the center of the tightest cluster in order to homogenize the pattern.
The void-and-cluster method consists of three distinct steps:
(A) generating the Prototype Binary Pattern;
(B) "homogenizing" the Prototype Binary Pattern by removing pixels from the clusters and assigning them to the voids to generate a homogenized Initial Binary Pattern; and
(C) assigning dither array threshold numbers to the resulting homogenized Initial Binary Pattern.
More specifically, the Prototype Binary Pattern is generated by using any convenient technique that generates an input pattern where not more than half the pixels are "1's" and the rest are "0's". For example, a white noise pattern will serve as the Prototype Binary Pattern.
The next step in the method is to find the "voids" and the "clusters" so that pixels can be moved between the voids and clusters. Voids and clusters are located by means of a filter which examines the neighboring pixels bordering each pixel being processed. In particular, a void-finding filter considers the neighborhood pixels around every majority pixel in the Prototype Binary Pattern and a cluster-finding filter considers the neighborhood pixels around every minority pixel. In the aforementioned articles, a two-dimensional Gaussian filter represented by the function: ##EQU1## is used in order to find voids and clusters. During this processing, the values in the array are repeatedly processed and a single pixel may be moved several times from cluster to void. This processing is performed iteratively until the voids stop getting smaller and the clusters stop getting looser. Processing is deemed complete when removing the "1" from the tightest cluster in the pattern creates the largest void. The resulting homogenized pattern is called the Initial Binary Pattern.
In accordance with the third step of the method, the dither array is built from the Initial Binary Pattern by assigning threshold values to the dither array using the Initial Binary Pattern. In performing this step, the Initial Binary Pattern and the dither array are manipulated in parallel in three phases in accordance with a predetermined algorithm. Threshold values are assigned to the dither array cells based on the "rank" value of the "1's" in the Initial Binary Pattern. In particular in Phase I, one minority pixel or "1" is removed at a time from the Initial Binary Pattern while, in parallel, the rank or the number of minority pixels remaining in the Initial Binary Pattern is entered into the dither array in the location corresponding to the location of the removed "1". In each case, the minority pixel that is removed is the pixel in the center of the tightest cluster.
In the second phase (Phase II) the Initial Binary Pattern is again used as the starting basis and one minority pixel (or "1") is inserted at a time into the Initial Binary Pattern while, in parallel, its rank is entered into the dither array. In each case, the minority pixel that is inserted is done so at the location of a "0" identified as the center of the largest void.
Finally, in Phase III the Initial Binary Pattern produced by adding "1's" in Phase II is used as the starting point. In Phase III, the meaning of "minority pixel" is reversed from "1" to "0" because there are more 1's than 0's in the Initial Binary Pattern due to "1's" being added in Phase II. The Initial Binary Pattern is now filled with more and more 1's while the dither array continues to be filled with the rank values. In each step a "1" is inserted in the "0" location identified in the tightest cluster of minority pixels. At the end of Phase III, the Initial Binary Pattern is filled with all 1's and the dither array is filled with a unique rank value in each element from 0 to the maximum of pixels.
While the void and cluster method produces a dither array that, in turn, generates high-quality halftoned images that are generally artifact-free there is still some tonal distortion and the resulting image can be further improved. All digital halftoning techniques assume perfectly square pixels, which fully cover the printable area of the recording medium. If this were truly the case, the printer output density would be directly proportional to the input (scanned) density of the original; the ideal case, as indicated by the 45.degree. line in FIG. 12, occurs when output density precisely matches input density. In fact, however, the response of real electronic printing devices is typically nonlinear because such devices do not generate perfectly adjacent, nonoverlapping square dots; instead, they tend to produce dots that are more round than square, and which extend beyond the square boundaries of ideal pixels. This is necessary to ensure that adjacent dots fully overlap without leaving uncolored space (so that, for example, fully colored fields are printed solidly, without uncolored gaps) under a variety of printing conditions. Because the dots are larger than what is assumed in the halftoning algorithm, a plot of printer output density (expressed in terms of normalized percentage dot area) as a function of input gray-scale density--with larger values along the axes corresponding to lower density values, so that the maximum density occurs at the origin--ordinarily follows a curve similar to f(x) (solid line) in FIG. 12; the printed image, accordingly, appears darker than it should. The precise form of f(x) is determined both by characteristics of the printer and the selected halftoning algorithm.
To compensate for this effect, the function f(x) is defined mathematically through piecewise density measurements and regression, and an inverse (transfer) function, f.sup.-1 (x), (dotted line) defined as well. The latter function, when applied to incoming source data, offsets the effects of the printer function, correcting the data so that processing by the halftoning algorithm will produce a printed output whose density characteristics more closely match that of the original.
Although this technique, known as "predistortion," produces printed output superior to unmodified halftoned image data, correction to the ideal linear response does not necessarily produce the most visually desirable printed copy. This is due to the complex interactions between the human visual system and the patterns produced by halftoning algorithms on a variety of scales. Subjective responses frequently vary with both the halftoning algorithm employed and the degree of predistortion. See, e.g., Trontelj et al., "Optimal Halftoning Algorithm Depends on Printing Resolution," SID 92 Digest at 749 (1992). The present invention is directed toward improving predistortion to enhance the visual appearance of printed output.
Commonly-assigned co-pending application Ser. No. 08/269,601, filed on Jul. 1, 1994 is directed to a printing apparatus and method in which multibit source data representing the density variations of an original or source image is modified by a filter function. The filtered data is then processed by a halftoning module that converts the data into a raster of single-bit data suitable for transfer to a printing device. Instead of conforming linearly to the input source data, the raster data specifies a density pattern lighter than that of the source image in highlight and upper midtone regions, and darker than that of the source image in shadow and lower midtone regions.
Moreover, the filter is applied to parameters associated with the halftone processing algorithm rather than to the source data. For example, in a dithering scheme that utilizes an array of threshold values, the filter function can be applied to these values such that, when the filtered values are applied in an inverse fashion to source data to produce the raster pattern, that pattern is weighted according to the desired nonlinear output function. This approach can generate considerable savings in processing load, since a single dither array is modified just once but is applied repeatedly to the source data. Using, for example, a 64.times.64 dither array, application of the filter function to each cell requires processing of 4,096 data values; by contrast, assuming a sampling density of 720.times.720 dots per inch for the source image, applying the filter function to each source-data value would require processing of over 40 million data points for each 8".times.10" document.
Typically, many digital halftoning techniques assume ideally shaped pixels such as square pixels, which fully cover the printable area of the recording medium. This is necessary to ensure that adjacent dots fully overlap without leaving uncolored space (so that, for example, fully colored fields are printed solidly, without uncolored gaps) under a variety of printing conditions. FIG. 6 illustrates a hardcopy output of a printer having a resolution of 1/dpi, where dpi is dots per inch. As shown therein, ideal pixels 1001-1004 are illustrated as "ON". It is noted, that there are no voids between adjacent pixels.
These ideally shaped pixels are in effect an approximation. Actual pixels are represented by dots generally more circular in shape. As is known by one of ordinary skill in the art, the size or radius of these dots is dependent on many factors including, for example, the printing mechanism, the ink and the recording sheet.
FIG. 7 is an example where the diameter of a dot printed for the pixel is equal to or less than 1/d where d is dots per inch or dpi. In other words the radius r is less than 1/(.sqroot.2 d). As shown therein, a void 1100 is present between dots representing pixels 1001a and 1002a. Accordingly, when two adjacent pixels are ON there will be portions having voids. This example produces unacceptable results and thus dots having a radius .ltoreq.1/(.sqroot.2 d) are avoided.
FIG. 8 is another example in which the radius of a dot representing a pixel is: ##EQU2##
As shown therein, there are no voids between dots of adjacent pixels, for example pixels 1001c and 1002c. However, the dots representing pixels 1001c and 1002c overlap in area 1200.
FIGS. 9-A and 9-B, illustrate another example of a dot representing a pixel having a radius of: ##EQU3##
FIG. 9-A shows for simplicity every other pixel on every other row. As shown therein every other pixel in the same row, for example, pixels 1000c and 1000c (or column, for example, pixels 1002d and 1003d) overlap. However the dots representing pixels 1001c and 1003c do not overlap. FIG. 9-B illustrates every pixels. As shown therein, the dot representing pixel 1004d provides redundant information since the dots representing pixels 1001d and 1002d occupy the area of pixel 1004d. As such, ink used to print pixel 1004d is unnecessary. Moreover, additional computations and printing time are required to print with every adjacent pixel. Typical values at 720 d of 1/dpi is 0.0014 inches, r is 0.0015 inches and .sqroot.2/d is 0.0020 inches.
Moreover for dots having this size, a plot of printer output density (expressed in terms of normalized percentage dot area) as a function of input gray-scale density--with larger values along the axes corresponding to lower density values, so that the maximum density occurs at the origin--ordinarily follows a curve similar to f(x) (dashed line) in FIG. 12; the printed image, accordingly, appears darker than it should. Additionally, as illustrated by its more rectangular in shape, the picture would have less dynamic range. Typically the dynamic range would be about half. As such the inverse (transfer) function, f.sup.-1 (x), (dashed-dotted line) also has about half the dynamic range.
FIGS. 10-A and 10-B illustrate the example in which a dot representing a pixel has a radius of: ##EQU4##
This example is similar to the example in FIGS. 9-A and 9-B, except the dots representing pixels 1001e and 1003e (referred to as alternate diagonal pixels) also intersect.
Conventional printers generally have a resolution of 300 to 360 dpi. Printers with higher resolutions may have a resolution of 720 dpi. As will appreciated, printing at 720 dpi has approximately 4 times the resolution as 360 dpi. In other words at 720 dpi a one inch square printing area contains 720.times.720 or 518,400 dots. On the other hand, a resolution of 360 dpi has 360.times.360 or 129,600 dots. However with current technology, using conventional printing mechanisms, ink and/or paper to print at 720 dpi the dot size obtainable is: ##EQU5## as shown in FIGS. 9-A and 9-B. As such, printing at 720 dpi with this dot size results in printing redundant information and requires additional computation and printing time.